use crate::key_types::{self, LookupKey};
use crate::types;

use std::cmp::Ordering;
use std::rc::Rc;

/// 这是一个类型别名，定义了一个可共享的 Cmp 实现。
///
/// dyn Cmp：表示任何实现了 Cmp trait 的类型（动态多态）
///
/// Box<dyn Cmp>：将比较器装箱，方便动态分发
///
/// Rc：引用计数指针，允许比较器被多个地方共享而不转移所有权
///
/// 这个类型通常用于需要在多个组件间共享同一个比较器实例的场景。
type WrappedCmp = Rc<Box<dyn Cmp>>;

/// Comparator trait, supporting types that can be nested (i.e., add additional functionality on
/// top of an inner comparator)
///
/// 定义了字节序列比较的核心操作，是实现键排序和范围划分的基础：
pub trait Cmp {
    /// Compare to byte strings, bytewise.
    ///
    /// 核心比较方法：比较两个字节序列 a 和 b 的大小，返回 Ordering（Less/Equal/Greater）。例如比较 b"abc" 和 b"abd" 时，应返回 Less。
    fn cmp(&self, a: &[u8], b: &[u8]) -> Ordering;

    /// Return the shortest byte string that compares "Greater" to the first argument and "Less" to
    /// the second one.
    ///
    /// 生成最短分隔符：找到一个字节序列，使得 from < 分隔符 < to，且该序列长度最短。用于划分两个键范围（如 SSTable 中相邻数据块的边界）。
    fn find_shortest_sep(&self, from: &[u8], to: &[u8]) -> Vec<u8>;
    /// Return the shortest byte string that compares "Greater" to the argument.
    ///
    /// 生成最短后继：找到一个比 key 大的最短字节序列。用于确定某个键的下一个可能边界（如范围查询的上限）。
    fn find_short_succ(&self, key: &[u8]) -> Vec<u8>;

    /// A unique identifier for a comparator. A comparator wrapper (like InternalKeyCmp) may
    /// return the id of its inner comparator.
    ///
    /// 返回比较器的唯一标识符。用于确保存储的数据与比较器匹配（不同比较器可能导致键排序方式不同，进而引发数据错误）。
    fn id(&self) -> &'static str;
}

/// The default byte-wise comparator.
///
/// 这是 Cmp trait 的默认实现，采用字节序比较（按字节逐个比较，类似字典序）。例如：
///
/// b"apple" < b"banana"（首字节 a < b）
///
/// b"app" < b"apple"（短序列在长序列前，且前缀匹配）
#[derive(Clone)]
pub struct DefaultCmp;

impl Cmp for DefaultCmp {

    /// 这段代码是 Cmp trait 中 cmp 方法的一个具体实现，其功能是按照字节序列的自然顺序（字节序）比较两个字节切片 a 和 b 的大小。
    ///
    /// 示例：
    ///
    /// a = b"abc"，b = b"abd" → 比较到第三个字节，a\[2] = 99（'c'） < b\[2] = 100（'d'）→ 返回 Ordering::Less。
    ///
    /// a = b"apple"，b = b"apply" → 比较到第四个字节，a\[3] = 108（'l'） < b\[3] = 121（'y'）→ 返回 Ordering::Less。
    ///
    /// a = b"test"，b = b"test" → 所有字节和长度都相等 → 返回 Ordering::Equal。
    fn cmp(&self, a: &[u8], b: &[u8]) -> Ordering {
        // a.cmp(b) 是 Rust 中字节切片（&[u8]）自带的比较方法，会按照字节序（lexicographical order） 逐个比较两个切片中的字节：
        // 从第一个字节开始比较，若 a[i] < b[i]，则返回 Ordering::Less；
        // 若 a[i] > b[i]，则返回 Ordering::Greater；
        // 若所有已比较的字节都相等，则较短的切片被视为较小（如 b"abc" < b"abcd"）；
        // 若长度和所有字节都相等，则返回 Ordering::Equal。
        // 这个实现直接将比较逻辑委托给 Rust 标准库的字节切片比较，是最基础、最常用的字节序列比较方式（例如 DefaultCmp 的 cmp 方法通常就这么实现）。
        a.cmp(b)
    }

    fn id(&self) -> &'static str {
        "leveldb.BytewiseComparator"
    }

    /// 这段代码实现了一个名为 find_shortest_sep 的函数，其核心功能是为两个字节数组 a 和 b 找到一个最短的分隔符（separator），使得这个分隔符满足：a < 分隔符 < b（按字节序比较）。
    ///
    /// 在 LevelDB 的 SSTable 中，索引块（index block）需要记录每个数据块的「最大键」，以快速定位目标键所在的数据块。
    /// find_shortest_sep 用于生成相邻数据块最大键之间的最短分隔符，既能保证索引准确性，又能最小化索引存储开销。
    ///
    /// 示例说明：
    ///
    /// 若两个数据块的最大键分别为 apple 和 banana，函数会生成最短分隔符（如 applf），确保所有落在 [apple, applf) 范围内的键都属于前一个数据块。
    ///
    /// 示例说明：
    ///
    /// 假设 a = [0x61, 0x62, 0x63]（对应字符串 "abc"），b = [0x61, 0x62, 0x66]（对应字符串 "abf"）。
    ///
    /// 比较公共前缀：前两个字节都是 0x61（'a'）和 0x62（'b'），差异位置 diff_at = 2。
    ///
    /// 检查 a\[2\] = 0x63（'c'），0x63 < 0xff 且 0x63 + 1 = 0x64 < 0x66（'f'），满足条件。
    ///
    /// 生成分隔符：取 a[0..3] 并将 0x63 加 1 → [0x61, 0x62, 0x64]（对应字符串 "abd"）。
    ///
    /// 最终结果：abc < abd < abf，且 "abd" 是满足条件的最短分隔符（长度与 a 相同，无需额外字节）。
    ///
    /// 这个函数通过最小化分隔符的长度，在保证索引准确性的同时减少了存储开销，是 LevelDB 等存储引擎中高效划分数据块范围的核心工具。
    fn find_shortest_sep(&self, a: &[u8], b: &[u8]) -> Vec<u8> {
        // 如果 a 和 b 完全相等（a == b），直接返回 a 的副本（此时分隔符就是其自身）。
        if a == b {
            return a.to_vec();
        }

        let min = if a.len() < b.len() { a.len() } else { b.len() };
        let mut diff_at = 0;
        // 遍历 a 和 b 的公共前缀，找到第一个字节不同的位置 diff_at（例如 a=abc、b=ade，差异位置在索引 1，a[1]='b' 而 b[1]='d'）。
        while diff_at < min && a[diff_at] == b[diff_at] {
            diff_at += 1;
        }

        // First, try to find a short separator. If that fails, try a backup mechanism below.
        while diff_at < min {
            let diff = a[diff_at];
            // 在差异位置 diff_at 检查：若 a[diff_at] 不是 0xff，且 a[diff_at]+1 小于 b[diff_at]，则将 a 中该位置的字节加 1 作为分隔符。
            // 例如：a=abc（[97,98,99]）、b=ade（[97,100,101]），差异位置 1 的 a[1]=98，98+1=99 < 100，因此分隔符为 a[0..2] 并将 98 加 1 → [97,99]（即 "ac"），满足 abc < ac < ade。
            if diff < 0xff && diff + 1 < b[diff_at] {
                let mut sep = Vec::from(&a[0..diff_at + 1]);
                sep[diff_at] += 1;
                assert!(self.cmp(&sep, b) == Ordering::Less);
                return sep;
            }

            diff_at += 1;
        }
        // 如果上述步骤失败（如差异位置无法直接加 1），从 a 的末尾向前找第一个非 0xff 的字节，将其加 1 并检查是否小于 b。
        // 若仍失败（如 a 全是 0xff），则在 a 末尾追加 0 字节（利用长度优势保证 a < 分隔符）。
        let mut sep = Vec::with_capacity(a.len() + 1);
        sep.extend_from_slice(a);
        // Try increasing a and check if it's still smaller than b. First find the last byte
        // smaller than 0xff, and then increment that byte. Only if the separator is lesser than b,
        // return it.
        // 从 a 的末尾向前找第一个不是 0xff 的字节，将其加 1（例如 a=abz（[97,98,122]），b=ab{（[97,98,123]），可将 z 加 1 得到 {| 作为分隔符）。
        let mut i = a.len() - 1;
        while i > 0 && sep[i] == 0xff {
            i -= 1;
        }
        if sep[i] < 0xff {
            sep[i] += 1;
            if self.cmp(&sep, b) == Ordering::Less {
                return sep;
            } else {
                sep[i] -= 1;
            }
        }

        // Backup case: either `a` is full of 0xff, or all different places are less than 2
        // characters apart.
        // The result is not necessarily short, but a good separator: e.g., "abc" vs "abd" ->
        // "abc\0", which is greater than abc and lesser than abd.
        // Append a 0 byte; by making it longer than a, it will compare greater to it.
        // 如果 a 全是 0xff（无法加 1），则在 a 末尾追加一个 0 字节（例如 a=ff → 分隔符为 ff\0）。由于长度增加，该分隔符必然大于 a，且通过字节序比较小于 b。
        sep.extend_from_slice(&[0]);
        sep
    }

    /// 这段代码定义了一个名为 find_short_succ 的函数，其功能是为给定的字节切片 a 找到一个 “最短的后继字节序列”。
    /// 简单来说，它会生成一个比输入 a 大的字节序列，且这个序列是满足条件的最短可能形式。
    ///
    fn find_short_succ(&self, a: &[u8]) -> Vec<u8> {
        // 首先将输入 a 复制到 result 中，作为初始值。
        let mut result = a.to_vec();
        // 遍历 a 的每个字节（i 从 0 到 a.len()-1）：
        for i in 0..a.len() {
            // 如果找到第一个值不等于 0xff 的字节（a[i] != 0xff）：
            if a[i] != 0xff {
                // 将该字节加 1（result[i] += 1）
                result[i] += 1;
                // 截断后续字节（result.resize(i + 1, 0)），只保留到当前位置
                result.resize(i + 1, 0);
                // 立即返回这个结果
                return result;
            }
        }
        // Rare path
        // 如果 a 的所有字节都是 0xff（循环完成后未返回）：
        // 在结果末尾追加一个 255（即 0xff）
        result.push(255);
        // 返回这个新序列
        result
    }
}

/// Same as memtable_key_cmp, but for InternalKeys.
///
/// 这段代码定义了一个名为 InternalKeyCmp 的结构体，它是一种包装了底层比较器的复合比较器，专门用于比较 LevelDB/RocksDB 等存储引擎中的「内部键（InternalKey）」。
///
/// 核心作用：
///
/// 在存储引擎中，「用户键（user key）」通常会被扩展为「内部键（InternalKey）」，内部键除了包含用户键本身，还会附加版本号（sequence number）和操作类型（如删除标记），用于实现多版本并发控制（MVCC）和事务等功能。
///
/// InternalKeyCmp 的作用就是提供针对这种内部键的比较逻辑，它通过包裹一个底层的用户键比较器（Rc<Box<dyn Cmp>>），在其基础上增加对内部键特有部分（版本号、操作类型）的比较规则。
///
/// 字段解析：
///
/// pub Rc<Box<dyn Cmp>>：这是被包裹的底层比较器，通常是用户指定的键比较器（如默认的字节序比较器 DefaultCmp）。
///
/// Rc 允许该比较器被多个组件共享。
///
/// Box<dyn Cmp> 提供动态多态能力，可适配任何实现了 Cmp trait 的比较器。
///
/// 典型使用场景：
///
/// 当需要比较两个内部键时，InternalKeyCmp 会：
///
/// 先使用底层比较器比较内部键中的「用户键」部分。
///
/// 如果用户键相同，再比较它们的版本号（通常版本号小的键更新）和操作类型，以确定最终顺序。
///
/// 这种设计既复用了用户定义的键比较逻辑，又添加了存储引擎内部所需的比较规则，是一种典型的装饰器模式（decorator pattern）应用。
///
/// 例如，假设两个内部键：
///
/// InternalKey("apple", 100, Put)（版本 100 的插入操作）
///
/// InternalKey("apple", 90, Delete)（版本 90 的删除操作）
///
/// InternalKeyCmp 会先比较用户键（都是 "apple" 相等），再比较版本号，最终判定版本 90 的键比版本 100 的键更新（因为在 LevelDB 中，版本号越小表示操作越新）。
#[derive(Clone)]
pub struct InternalKeyCmp(pub Rc<Box<dyn Cmp>>);

impl Cmp for InternalKeyCmp {
    fn cmp(&self, a: &[u8], b: &[u8]) -> Ordering {
        key_types::cmp_internal_key(self.0.as_ref().as_ref(), a, b)
    }

    fn id(&self) -> &'static str {
        self.0.id()
    }

    /// 这段代码是对 find_shortest_sep 函数的进一步封装，专门用于 LevelDB 内部键（InternalKey）的最短分隔符生成。
    /// 它在基础的字节数组分隔符逻辑上，增加了对 LevelDB 内部键结构的处理，确保生成的分隔符符合 LevelDB 的版本控制和键排序规则。
    ///
    /// 为两个 内部键（InternalKey）a 和 b 生成最短分隔符，满足：a < 分隔符 < b（按 LevelDB 内部键的排序规则）。
    ///
    /// LevelDB 的内部键格式为：\[用户键（UserKey）] + \[序列号（SequenceNumber）] + \[值类型（ValueType）]，其中序列号用于版本控制（大序列号表示更新的数据），值类型区分正常数据和删除标记。
    ///
    /// 在 LevelDB 中，内部键的排序规则是：先按用户键字典序排序，用户键相同则按序列号降序排序。这段代码生成的分隔符严格遵循该规则，主要用于：
    ///
    /// SSTable 索引块中数据块边界的标记（确保查询时能准确定位数据块）。
    ///
    /// 压缩（Compaction）过程中合并数据时，保持键的有序性和版本正确性。
    ///
    /// 通过处理内部键的特殊结构（用户键 + 序列号），确保生成的分隔符既能最小化存储开销，又能正确反映 LevelDB 的数据版本关系。
    fn find_shortest_sep(&self, a: &[u8], b: &[u8]) -> Vec<u8> {
        // 如果 a 和 b 完全相同，直接返回 a 的副本（此时分隔符就是其自身）。
        if a == b {
            return a.to_vec();
        }
        // parse_internal_key 函数将内部键 a 和 b 拆分为三部分：值类型（忽略，用 _ 表示）、序列号（seqa 是 a 的序列号）、用户键（keya 是 a 的用户键，keyb 是 b 的用户键）。
        // 核心：分隔符的生成主要基于 用户键（keya 和 keyb），因为 LevelDB 首先按用户键排序，再按序列号（降序）排序。
        let (_, seqa, keya) = key_types::parse_internal_key(a);
        let (_, _, keyb) = key_types::parse_internal_key(b);
        // 调用底层的 find_shortest_sep 为用户键 keya 和 keyb 生成最短分隔符 sep（即上一个问题中分析的基础字节数组分隔符逻辑）。
        let sep: Vec<u8> = self.0.find_shortest_sep(keya, keyb);
        // 若 sep 的长度小于 keya 且 keya < sep，则用 MAX_SEQUENCE_NUMBER（最大序列号）构造内部键。
        // 原因：短用户键在 LevelDB 排序中具有特殊性，搭配最大序列号可确保分隔符大于 a。
        if sep.len() < keya.len() && self.0.cmp(keya, &sep) == Ordering::Less {
            return LookupKey::new(&sep, types::MAX_SEQUENCE_NUMBER)
                .internal_key()
                .to_vec();
        }
        // 否则，使用 a 的序列号 seqa 构造内部键，确保分隔符在 a 和 b 之间。
        LookupKey::new(&sep, seqa).internal_key().to_vec()
    }

    /// 这段代码是 InternalKeyCmp 结构体中实现的 find_short_succ 方法，用于为内部键（InternalKey）生成最短的后继键。
    /// 它在底层用户键的后继键基础上，保留了内部键的版本信息，确保生成的后继键符合存储引擎内部的键比较规则。
    ///
    /// 核心作用：
    ///
    /// 在存储引擎中，内部键的比较不仅要看用户键，还要看版本号。这个方法确保生成的后继键：
    ///
    /// 用户键部分是原用户键的最短后继（符合 find_short_succ 的语义）
    ///
    /// 保留原有的版本号 seq（维持内部键的版本信息）
    ///
    /// 最终生成的内部键整体大于原内部键（满足 后继键 的定义）
    ///
    /// 示例：
    ///
    /// 假设输入内部键 a 解析后：
    ///
    /// 用户键 key = b"apple"
    ///
    /// 版本号 seq = 100
    ///
    /// 底层比较器为 key 生成最短后继 succ = b"applf"
    ///
    /// 用 succ 和 seq=100 构建新内部键，最终结果为包含 b"applf"、版本号 100 和操作类型的内部键字节序列
    ///
    /// 这个新内部键满足：a < 新内部键（按内部键规则比较），且是最短的可能形式
    ///
    /// 这一功能主要用于存储引擎的范围查询和索引构建，确保能高效划分内部键的范围。
    fn find_short_succ(&self, a: &[u8]) -> Vec<u8> {
        // 首先将输入的内部键 a 解析为三部分：
        // 忽略的操作类型（第一个返回值，用 _ 表示）
        // 版本号 seq（sequence number，用于多版本控制）
        // 原始用户键 key（用户实际传入的键）
        let (_, seq, key) = key_types::parse_internal_key(a);
        // 调用底层比较器（self.0，即被 InternalKeyCmp 包裹的 Cmp 实例）的 find_short_succ 方法，为用户键 key 生成最短后继键 succ（例如用户键是 "apple"，可能生成 "applf"）。
        let succ: Vec<u8> = self.0.find_short_succ(key);
        // 使用生成的用户键后继 succ 和原内部键的版本号 seq，创建一个新的内部键：
        // LookupKey::new 是构建内部键的工具
        // 最终返回完整的内部键字节序列（包含用户键后继、版本号和默认操作类型）
        LookupKey::new(&succ, seq).internal_key().to_vec()
    }
}

impl InternalKeyCmp {
    /// cmp_inner compares a and b using the underlying comparator (the "user comparator").
    pub fn cmp_inner(&self, a: &[u8], b: &[u8]) -> Ordering {
        self.0.cmp(a, b)
    }
}

/// An internal comparator wrapping a user-supplied comparator. This comparator is used to compare
/// memtable keys, which contain length prefixes and a sequence number.
/// The ordering is determined by asking the wrapped comparator; ties are broken by *reverse*
/// ordering the sequence numbers. (This means that when having an entry abx/4 and seRching for
/// abx/5, then abx/4 is counted as "greater-or-equal", making snapshot functionality work at all)
///
/// 这段代码定义了 MemtableKeyCmp 结构体，它是一个包装了用户提供的比较器的内部比较器，专门用于比较内存表（memtable）中的键。
/// 内存表是 LevelDB/RocksDB 等存储引擎中用于临时存储最新写入数据的结构，其键的格式和比较规则有特殊要求。
///
/// MemtableKeyCmp 的主要功能是定义内存表中键（memtable keys）的比较规则，这种键通常包含三部分信息：
///
/// 长度前缀（标识键的长度）
///
/// 用户键（user key，应用程序传入的键）
///
/// 序列号（sequence number，用于多版本控制）
///
/// 其比较规则的核心特点是：
///
/// 首先使用包装的用户比较器（Rc<Box<dyn Cmp>>）比较用户键部分。
///
/// 当用户键相同时，通过反向比较序列号来打破平局（即序列号小的键被视为更大）。
///
/// 字段解析：
///
/// pub Rc<Box<dyn Cmp>>：被包裹的用户比较器，负责用户键的基本比较逻辑（如字节序比较）。
///
/// Rc 允许比较器被多个组件共享而不转移所有权。
///
/// Box<dyn Cmp> 支持动态多态，可适配任何实现了 Cmp trait 的比较器。
///
/// 关键比较逻辑说明：
///
/// 注释中提到的核心规则：当用户键相同时，按序列号的反向排序。例如：
///
/// 键 A：abx/4（用户键 abx，序列号 4）
///
/// 键 B：abx/5（用户键 abx，序列号 5）
///
/// 按照 MemtableKeyCmp 的规则：
///
/// 先比较用户键（均为 abx，相等）
///
/// 再比较序列号，反向排序（4 < 5 → 键 A 被视为大于键 B）
///
/// 这一规则的目的是：
///
/// 确保同一用户键的多个版本中，最新版本（序列号小的，因为序列号随写入递增）排在前面，便于快速获取最新数据。
///
/// 支持快照（snapshot）功能：当查询某个快照版本时，可通过序列号过滤出该快照时间点之前的最新数据。
///
/// 典型使用场景：
///
/// 在内存表中插入、查询或迭代键时，MemtableKeyCmp 用于维持键的有序性，确保：
///
/// 不同用户键按用户比较器的规则排序。
///
/// 相同用户键的不同版本按序列号反向排序（最新版本在前）。
///
/// 这种设计是存储引擎实现多版本并发控制（MVCC）和高效读写的基础。
#[derive(Clone)]
pub struct MemtableKeyCmp(pub Rc<Box<dyn Cmp>>);

impl Cmp for MemtableKeyCmp {
    fn cmp(&self, a: &[u8], b: &[u8]) -> Ordering {
        key_types::cmp_memtable_key(self.0.as_ref().as_ref(), a, b)
    }

    fn id(&self) -> &'static str {
        self.0.id()
    }

    // The following two impls should not be used (by principle) although they should be correct.
    // They will crash the program.
    fn find_shortest_sep(&self, _: &[u8], _: &[u8]) -> Vec<u8> {
        panic!("find* functions are invalid on MemtableKeyCmp");
    }

    fn find_short_succ(&self, _: &[u8]) -> Vec<u8> {
        panic!("find* functions are invalid on MemtableKeyCmp");
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use key_types::LookupKey;

    #[test]
    fn test_cmp_defaultcmp_shortest_sep() {
        assert_eq!(
            DefaultCmp.find_shortest_sep("abcd".as_bytes(), "abcf".as_bytes()),
            "abce".as_bytes()
        );
        assert_eq!(
            DefaultCmp.find_shortest_sep("abc".as_bytes(), "acd".as_bytes()),
            "abd".as_bytes()
        );
        assert_eq!(
            DefaultCmp.find_shortest_sep("abcdefghi".as_bytes(), "abcffghi".as_bytes()),
            "abce".as_bytes()
        );
        assert_eq!(
            DefaultCmp.find_shortest_sep("a".as_bytes(), "a".as_bytes()),
            "a".as_bytes()
        );
        assert_eq!(
            DefaultCmp.find_shortest_sep("a".as_bytes(), "b".as_bytes()),
            "a\0".as_bytes()
        );
        assert_eq!(
            DefaultCmp.find_shortest_sep("abc".as_bytes(), "zzz".as_bytes()),
            "b".as_bytes()
        );
        assert_eq!(
            DefaultCmp.find_shortest_sep("yyy".as_bytes(), "z".as_bytes()),
            "yyz".as_bytes()
        );
        assert_eq!(
            DefaultCmp.find_shortest_sep("".as_bytes(), "".as_bytes()),
            "".as_bytes()
        );
    }

    #[test]
    fn test_cmp_defaultcmp_short_succ() {
        assert_eq!(
            DefaultCmp.find_short_succ("abcd".as_bytes()),
            "b".as_bytes()
        );
        assert_eq!(
            DefaultCmp.find_short_succ("zzzz".as_bytes()),
            "{".as_bytes()
        );
        assert_eq!(DefaultCmp.find_short_succ(&[]), &[0xff]);
        assert_eq!(
            DefaultCmp.find_short_succ(&[0xff, 0xff, 0xff]),
            &[0xff, 0xff, 0xff, 0xff]
        );
    }

    #[test]
    fn test_cmp_internalkeycmp_shortest_sep() {
        let cmp = InternalKeyCmp(Rc::new(Box::new(DefaultCmp)));
        assert_eq!(
            cmp.find_shortest_sep(
                LookupKey::new("abcd".as_bytes(), 1).internal_key(),
                LookupKey::new("abcf".as_bytes(), 2).internal_key()
            ),
            LookupKey::new("abce".as_bytes(), 1).internal_key()
        );
        assert_eq!(
            cmp.find_shortest_sep(
                LookupKey::new("abcd".as_bytes(), 1).internal_key(),
                LookupKey::new("abce".as_bytes(), 2).internal_key()
            ),
            LookupKey::new("abcd\0".as_bytes(), 1).internal_key()
        );
        assert_eq!(
            cmp.find_shortest_sep(
                LookupKey::new("abc".as_bytes(), 1).internal_key(),
                LookupKey::new("zzz".as_bytes(), 2).internal_key()
            ),
            LookupKey::new("b".as_bytes(), types::MAX_SEQUENCE_NUMBER).internal_key()
        );
        assert_eq!(
            cmp.find_shortest_sep(
                LookupKey::new("abc".as_bytes(), 1).internal_key(),
                LookupKey::new("acd".as_bytes(), 2).internal_key()
            ),
            LookupKey::new("abd".as_bytes(), 1).internal_key()
        );
        assert_eq!(
            cmp.find_shortest_sep(
                LookupKey::new("abc".as_bytes(), 1).internal_key(),
                LookupKey::new("abe".as_bytes(), 2).internal_key()
            ),
            LookupKey::new("abd".as_bytes(), 1).internal_key()
        );
        assert_eq!(
            cmp.find_shortest_sep(
                LookupKey::new("".as_bytes(), 1).internal_key(),
                LookupKey::new("".as_bytes(), 2).internal_key()
            ),
            LookupKey::new("".as_bytes(), 1).internal_key()
        );
        assert_eq!(
            cmp.find_shortest_sep(
                LookupKey::new("abc".as_bytes(), 2).internal_key(),
                LookupKey::new("abc".as_bytes(), 2).internal_key()
            ),
            LookupKey::new("abc".as_bytes(), 2).internal_key()
        );
    }

    #[test]
    fn test_cmp_internalkeycmp() {
        let cmp = InternalKeyCmp(Rc::new(Box::new(DefaultCmp)));
        // a < b < c
        let a = LookupKey::new("abc".as_bytes(), 2).internal_key().to_vec();
        let b = LookupKey::new("abc".as_bytes(), 1).internal_key().to_vec();
        let c = LookupKey::new("abd".as_bytes(), 3).internal_key().to_vec();
        let d = "xyy".as_bytes();
        let e = "xyz".as_bytes();

        assert_eq!(Ordering::Less, cmp.cmp(&a, &b));
        assert_eq!(Ordering::Equal, cmp.cmp(&a, &a));
        assert_eq!(Ordering::Greater, cmp.cmp(&b, &a));
        assert_eq!(Ordering::Less, cmp.cmp(&a, &c));
        assert_eq!(Ordering::Less, cmp.cmp_inner(d, e));
        assert_eq!(Ordering::Greater, cmp.cmp_inner(e, d));
    }

    #[test]
    #[should_panic]
    fn test_cmp_memtablekeycmp_panics() {
        let cmp = MemtableKeyCmp(Rc::new(Box::new(DefaultCmp)));
        cmp.cmp(&[1, 2, 3], &[4, 5, 6]);
    }
}
